\documentclass[a4paper,10pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{cite}
\usepackage[brazil]{babel}
\usepackage[T1]{fontenc}
\usepackage{graphicx}

\newcommand{\cedil}{\c{c}}
\newcommand{\Cedil}{\C{c}}

% Title Page
\title{\textbf{Computa\cedil\~ao Paralela GB-100}\\ {C\'alculo da norma euclidiana}}
\author{Laborat\'orio Nacional de Computa\cedil\~ao Cient\'ifica \\ Av. Get\'ulio Vargas, 333. Sala 1A-24\\Pedro Henrique Marques Lira\\ \texttt{pedrohml@gmail.com}}
\date{}

\begin{document}
 \maketitle

\section{Introdu\cedil\~ao}
Este trabalho implementa o c\'alculo da norma euclidiana vetorial, ou seja, a norma euclidiana $N$ do vetor $\vec{V} = (e_1, e_2, ..., e_n)$ \'e dada por:

\begin{displaymath}
 N (\vec{V}) = \sqrt{e_{1}^2 + e_{2}^2 + \cdots + e_n^2}
\end{displaymath}

\section{Implementa\cedil\~ao}

A implementa\cedil\~ao est\'a dividida em tr\^es programas utilizando tecnologias e fun\cedil\~oes diferentes para troca de mensagens. S\~ao elas:
\begin{itemize}
 \item \textbf{MPI\_Send, MPI\_Recv}: Realiza troca de mensagens $1:1$ entre os processos com mem\'oria distribu\'ida.
 \item \textbf{MPI\_Reduce}: Realiza troca de mensagens $N:1$ entre os processos e agrega os dados utilizando opera\cedil\~oes matem\'aticas definidas no MPI com mem\'oria distribu\'ida.
 \item \textbf{OpenMP}: Realiza as opera\cedil\~oes em mem\'oria compartilhada e atrav\'es de \emph{threads} com o operador \emph{\#pragma omp reduction}.
\end{itemize}


A implementa\cedil\~ao foi realizada na linguagem C da seguinte forma:

\begin{enumerate}
  \item O vetor \'e inicializado por padr\~ao com 1.0, podendo ser alterado via argumento do programa.
  \item Cria\cedil\~ao da fun\cedil\~ao \emph{parcialsquaresum} que faz o c\'alculo parcial da soma dos quadrados do vetor, para que possamos dividir o c\'alculo entre os processos;
  \item A distribui\cedil\~ao do c\'alculo em MPI \'e feito na forma reversa da seguinte forma:
	\begin{verbatim}
liminf = (int)ceil((size-(rank+1))*piecesize);
limsup = (int)floor((size-(rank))*piecesize);
if (rank==0){
      limsup = VECTOR_SIZE;
}
	\end{verbatim}
  Onde, \emph{rank} e \emph{size} representam o n\'umero do processo e a quantidade total destes, respectivamente. Com esse c\'alculo o processo de \emph{rank} igual a 0 calcular\'a os elementos excedentes da divis\~ao $piecesize= \frac{(VECTOR\_SIZE+1)}{size}$, sendo $VECTOR\_SIZE$ o tamanho do vetor e $size$ o n\'umero de processos.
 \item Utilizando OpenMP o c\'alculo \'e feito da seguinte forma:
\begin{verbatim}
#pragma omp parallel private(rank) shared(size) reduction(+:sum)
{
      size = omp_get_num_threads();
      #pragma omp for 
      for (k=0;k<vector_size;k++){
            rank = omp_get_thread_num();
            sum += exp2(vec[k]);
      }
}
\end{verbatim}
Onde, no final teremos a vari\'avel \emph{sum} retornando o valor total do c\'alculo.

\end{enumerate}

Para simular um \emph{delay} no c\'alculo da pot\^encia ao quadrado, $delay = 0.002s$:
\begin{verbatim}
//simulacao de delay no produto de dois elementos
inline real exp2(real element){
        usleep(2000);
        return element*element;
}

//funcao de calculo parcial da soma dos quadrados
inline real parcialsquaresum(real *vec,int liminf, int limsup){
        register int k; //utiliza registrador do processador se possivel
        real result = 0.0;
        for (k=liminf;k<limsup;k++){
                result += exp2(vec[k]);
        }
        return result;
}
\end{verbatim}


\section{Resultados}

\begin{itemize}
 \item Local: Laborat\'orio 4
 \item S.O.: GNU/Linux
 \item hostfile:
	\begin{verbatim}
		lab4mc01
		lab4mc03
		lab4mc05
		lab4mc06
		lab4mc07
		lab4mc09
		lab4mc11
		lab4mc14
		lab4mc15 
	\end{verbatim}
\end{itemize}

\subsection{MPI\_Send,MPI\_Recv}

Resultado para vetor inicializado com 1.0, de tamanho 2000, rodado em 18 processos:
{\scriptsize
\begin{verbatim}
###>mpirun -np 18 -hostfile hostfile.txt src/mpiexp_sendrecv 2000

(9,18) lab4mc01: Calculando soma dos quadrados do vector da posicao 888 a 999 = 111.00
(2,18) lab4mc05: Calculando soma dos quadrados do vector da posicao 1665 a 1776 = 111.00
(7,18) lab4mc14: Calculando soma dos quadrados do vector da posicao 1110 a 1221 = 111.00
(10,18) lab4mc03: Calculando soma dos quadrados do vector da posicao 777 a 888 = 111.00
(4,18) lab4mc07: Calculando soma dos quadrados do vector da posicao 1443 a 1554 = 111.00
(6,18) lab4mc11: Calculando soma dos quadrados do vector da posicao 1221 a 1332 = 111.00
(12,18) lab4mc06: Calculando soma dos quadrados do vector da posicao 555 a 666 = 111.00
(5,18) lab4mc09: Calculando soma dos quadrados do vector da posicao 1332 a 1443 = 111.00
(1,18) lab4mc03: Calculando soma dos quadrados do vector da posicao 1776 a 1887 = 111.00
(3,18) lab4mc06: Calculando soma dos quadrados do vector da posicao 1554 a 1665 = 111.00
(14,18) lab4mc09: Calculando soma dos quadrados do vector da posicao 333 a 444 = 111.00
(16,18) lab4mc14: Calculando soma dos quadrados do vector da posicao 111 a 222 = 111.00
(11,18) lab4mc05: Calculando soma dos quadrados do vector da posicao 666 a 777 = 111.00
(13,18) lab4mc07: Calculando soma dos quadrados do vector da posicao 444 a 555 = 111.00
(15,18) lab4mc11: Calculando soma dos quadrados do vector da posicao 222 a 333 = 111.00
(8,18) lab4mc15: Calculando soma dos quadrados do vector da posicao 999 a 1110 = 111.00
(17,18) lab4mc15: Calculando soma dos quadrados do vector da posicao 0 a 111 = 111.00
Resultado total: 2000.000000
Norma do vetor: 44.72135954999579392818
(0,18) lab4mc01: Calculando soma dos quadrados do vector da posicao 1887 a 2000 = 113.00
\end{verbatim}
}

Resultado para vetor inicializado com 3.0, de tamanho 2000,rodado em 9 processos:
{\scriptsize
\begin{verbatim}
###> mpirun -np 9 -hostfile hostfile.txt src/mpiexp_sendrecv 2000 3.0

(1,9) lab4mc03: Calculando soma dos quadrados do vector da posicao 1554 a 1776 = 1998.00
(3,9) lab4mc06: Calculando soma dos quadrados do vector da posicao 1110 a 1332 = 1998.00
(6,9) lab4mc11: Calculando soma dos quadrados do vector da posicao 444 a 666 = 1998.00
(2,9) lab4mc05: Calculando soma dos quadrados do vector da posicao 1332 a 1554 = 1998.00
(4,9) lab4mc07: Calculando soma dos quadrados do vector da posicao 888 a 1110 = 1998.00
(7,9) lab4mc14: Calculando soma dos quadrados do vector da posicao 222 a 444 = 1998.00
(8,9) lab4mc15: Calculando soma dos quadrados do vector da posicao 0 a 222 = 1998.00
Resultado total: 18000.000000
(5,9) lab4mc09: Calculando soma dos quadrados do vector da posicao 666 a 888 = 1998.00
Norma do vetor: 134.16407864998738178455
(0,9) lab4mc01: Calculando soma dos quadrados do vector da posicao 1776 a 2000 = 2016.00
\end{verbatim}
}

\subsection{MPI\_Reduce}

Resultado para vetor inicializado com 5.0, de tamanho 3000,rodado em 18 processos:
{\scriptsize
\begin{verbatim}
###> mpirun -np 18 -hostfile hostfile.txt src/mpiexp_sendrecv 3000 5.0

(9,18) lab4mc01: Calculando soma dos quadrados do vector da posicao 1328 a 1494 = 4150.00
(1,18) lab4mc03: Calculando soma dos quadrados do vector da posicao 2656 a 2822 = 4150.00
(2,18) lab4mc05: Calculando soma dos quadrados do vector da posicao 2490 a 2656 = 4150.00
(3,18) lab4mc06: Calculando soma dos quadrados do vector da posicao 2324 a 2490 = 4150.00
(8,18) lab4mc15: Calculando soma dos quadrados do vector da posicao 1494 a 1660 = 4150.00
(7,18) lab4mc14: Calculando soma dos quadrados do vector da posicao 1660 a 1826 = 4150.00
(13,18) lab4mc07: Calculando soma dos quadrados do vector da posicao 664 a 830 = 4150.00
(6,18) lab4mc11: Calculando soma dos quadrados do vector da posicao 1826 a 1992 = 4150.00
(4,18) lab4mc07: Calculando soma dos quadrados do vector da posicao 2158 a 2324 = 4150.00
(15,18) lab4mc11: Calculando soma dos quadrados do vector da posicao 332 a 498 = 4150.00
(17,18) lab4mc15: Calculando soma dos quadrados do vector da posicao 0 a 166 = 4150.00
(10,18) lab4mc03: Calculando soma dos quadrados do vector da posicao 1162 a 1328 = 4150.00
(11,18) lab4mc05: Calculando soma dos quadrados do vector da posicao 996 a 1162 = 4150.00
(16,18) lab4mc14: Calculando soma dos quadrados do vector da posicao 166 a 332 = 4150.00
(14,18) lab4mc09: Calculando soma dos quadrados do vector da posicao 498 a 664 = 4150.00
(5,18) lab4mc09: Calculando soma dos quadrados do vector da posicao 1992 a 2158 = 4150.00
(12,18) lab4mc06: Calculando soma dos quadrados do vector da posicao 830 a 996 = 4150.00
Resultado total: 75000.000000
Norma do vetor: 273.86127875258305672848
(0,18) lab4mc01: Calculando soma dos quadrados do vector da posicao 2822 a 3000 = 4450.00
\end{verbatim}
}

Resultado para vetor inicializado com 8.0, de tamanho 5000,rodado em 9 processos:
{\scriptsize
\begin{verbatim}
###> mpirun -np 9 -hostfile hostfile.txt src/mpiexp_reduce 5000 8.0
(1,9) lab4mc03: Calculando soma dos quadrados do vector da posicao 3885 a 4440 = 35520.00
(7,9) lab4mc14: Calculando soma dos quadrados do vector da posicao 555 a 1110 = 35520.00
(2,9) lab4mc05: Calculando soma dos quadrados do vector da posicao 3330 a 3885 = 35520.00
(6,9) lab4mc11: Calculando soma dos quadrados do vector da posicao 1110 a 1665 = 35520.00
(3,9) lab4mc06: Calculando soma dos quadrados do vector da posicao 2775 a 3330 = 35520.00
(4,9) lab4mc07: Calculando soma dos quadrados do vector da posicao 2220 a 2775 = 35520.00
(8,9) lab4mc15: Calculando soma dos quadrados do vector da posicao 0 a 555 = 35520.00
Resultado total: 320000.000000
(5,9) lab4mc09: Calculando soma dos quadrados do vector da posicao 1665 a 2220 = 35520.00
Norma do vetor: 565.68542494923801952067
(0,9) lab4mc01: Calculando soma dos quadrados do vector da posicao 4440 a 5000 = 35840.00
\end{verbatim}
}

\subsection{OpenMP}
Resultado para vetor inicializado com 8.0, de tamanho 5000,rodado em 6 threads:

{\scriptsize
\begin{verbatim}
###> ./openmp 5000 8.0
(0,6) Calculando soma dos quadrados do vector da posicao = 53376.000
(1,6) Calculando soma dos quadrados do vector da posicao = 53376.000
(2,6) Calculando soma dos quadrados do vector da posicao = 53376.000
(3,6) Calculando soma dos quadrados do vector da posicao = 53376.000
(4,6) Calculando soma dos quadrados do vector da posicao = 53376.000
(5,6) Calculando soma dos quadrados do vector da posicao = 53120.000
Resultado final da soma: 320000.000
Resultado final da norma: 565.68542494923801952067
\end{verbatim}
}

Resultado para vetor inicializado com 9.0, de tamanho 11000,rodado em 4 threads:

{\scriptsize
\begin{verbatim}
###> ./openmp 11000 9.0
(2,4) Calculando soma dos quadrados do vector da posicao = 222750.000
(0,4) Calculando soma dos quadrados do vector da posicao = 222750.000
(1,4) Calculando soma dos quadrados do vector da posicao = 222750.000
(3,4) Calculando soma dos quadrados do vector da posicao = 222750.000
Resultado final da soma: 891000.000
Resultado final da norma: 943.92796335313639229230
\end{verbatim}
}

\end{document}
